package pers.qianyu.month_202101.date_20210112;

import org.junit.*;

import java.util.*;

/**
 * 210. 课程表 II
 * https://leetcode-cn.com/problems/course-schedule-ii/
 *
 * @author mizzle rain
 * @date 2021-01-11 23:27
 */
public class FindOrder {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) map.put(i, new ArrayList<>());
        int[] edges = new int[numCourses];
        for (int[] p : prerequisites) {
            map.get(p[1]).add(p[0]);
            edges[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (edges[i] == 0) q.offer(i);
        int count = 0;
        int[] res = new int[numCourses];
        while (!q.isEmpty()) {
            int num = q.poll();
            res[count++] = num;
            for (int i : map.get(num)) {
                edges[i]--;
                if (edges[i] == 0) q.offer(i);
            }
        }
        if (count != numCourses) return new int[0];
        return res;
    }

    @Test
    public void test1() {
        int[] result = new FindOrder().findOrder(2, new int[0][0]);
        System.out.println("result = " + Arrays.toString(result));
    }
}
